In ATM networks the cells are transmitted over connections established from one end to another end of the network. The cells corresponding to one connection are conveyed through a series of network nodes. Nodes 1 and 4 in FIG. 1 are access nodes located at the boundary of the ATM network providing the user interface to the network; the other nodes (2, 3) are intermediate ATM network nodes; the connection represented on the figure is established between a user A and a user B. The access nodes of the ATM network have the responsibility of data integrity checking which is performed as for many digital transmission networks via FCS which is a data integrity checking code based on Cyclic Redundancy Check codes. CRC codes are generated by a generator polynomial characterizing the type of CRC; their calculations are described in `Teleinformatique I` of Henri Nussbaumer, 1987, Presses informatiques romandes CH-1015 Lausanne. The FCS which is a code derived from CRC has been standardized for data integrity checking as described in the ANSI X3.139-1987 document pages 28 and 29 and in the Appendix B.
In ATM networks different types of connections may be established depending on the quality of service required. Some ATM standards organizations ITU-T or The International Telecommunication Union--Telecommunication and ETSI or The European Telecommunication Standardization Institute have standardized different ATM Adaptation Layers (AALs) to provide generalized interworking across the ATM network. In the case of data, this AAL function takes frames (blocks) of data delivered to the ATM network, breaks them up into cells and adds necessary header information to allow rebuilding of the original block at the receiver, usually, the header of the cell includes ordering information to reassemble the segmented message. The AAL function involves checking for errors. This function is implemented in the access nodes 1 and 4 as illustrated in the FIG. 1. Different AALs correspond to different traffic types. For instance, if AAL1 is used for the service class A, circuit emulation, AAL3/4 provides an end-to-end transport for both connection oriented (class C) and connectionless data (class D). AAL5 is designed to operate significantly more efficiently than is AAL3/4. It has become the I.364 ITU-T standard. The implementation of the AAL5 function in the access nodes is characterized by its low cost, compared to the other AAL implementations, in terms of overhead in the network nodes. Particularly, a FCS code is used for error checking which is calculated with the CRC-32 codes generated by the generator polynomial of degree 32 already used for the Ethernet protocol.
Coming back to FIG. 1, the messages sent over one AAL5 connection from the source (A) are segmented in the access node (1) into sequences of segments of 48 bytes, the segments constituting the payload of the ATM cells which are sequentially sent over the connection. With AAL5, only the last cell of one message is identified as such with a `end of message` bit set in the header of the cell. During the segmenting of the message in the access node (1), the last cell constituting the last segment of the message is padded with zeros if necessary, the FCS of the message is calculated and added in the last 4 bytes of the payload. At the other end of the network, the network access node (4) near the second user (B) receiving the cells containing the message is in charge of reassembling it from the cells received. The segmenting and reassembling operations on a message is shown in FIG. 2. The hatched areas represent the parts of the initial message conveyed in the payload of the data cells. In the example of FIG. 2 the message has been split into four cells; the first cells of the cells flow convey 48 bytes of message in their payloads (21, 22, 23); the last cell (24) conveys less than 44 bytes (24) the remaining bytes is padded with zeros; the last four bytes of the last cell (25) is the FCS calculated on the bits stream of the message; this code is based on CRC-32 codes based on the standardized generator polynomial of degree 32; the FCS is calculated in the segmenting access node at the entry of the ATM network. The reassembling access node reassemble the entire message (250) in the correct order from the message segments conveyed in the cells. In the reassembling access node, a FCS of the bits stream constituted of the ordered cells payloads (including the padding and the FCS field for the last cell payload) needs to be calculated for the message integrity checking. Due to the well known properties of the FCS, the FCS calculated in the reassembling node is expected to be a known fixed value.
As explained hereunder, the FCS calculated in the reassembling node for data integrity checking will be performed progressively at each arrival of an AAL5 type cell. It appears that the methods known from the prior art for progressive calculation of the FCS are not efficient enough to support the cell rate of medium and high speed ATM lines (OC3 and above).
The FCS of the AAL5 connections is based on CRC-32 calculations. We can represent bits streams as polynomials having coefficients values of 0 or 1, each power of X representing the weight of the bit in the stream. The addition of such polynomials correspond to logical addition (XORs) on their coefficients. The FCS codes of messages transported via AAL5 cells belong to the Galois Field generated by the following generator polynomial : EQU G(X)=X.sup.32 +X.sup.26 +X.sup.23 +X.sup.22 +X.sup.16 +X.sup.12 +X.sup.11 +X.sup.10 +X.sup.8 +X.sup.7 +X.sup.5 +X.sup.4 +X.sup.2 +X+1
This generator polynomial of degree 32 has been standardized for error checking in Ethernet and then chosen by the ATM standard for AAL5 error checking.
The polynomial representation of a CRC code of a bits stream represented by the polynomial P(X) is the remainder of the polynomial division of P(X) by the generator polynomial G(X). The remainders of degree smaller than 32, form a Galois Field having a finite number of elements. One property of the Galois Field is to have a root .alpha., an irreducible polynomial of the Galois Field, characterized in that each element of the Galois Field is represented by .alpha..sup.d, d being one integer greater or equal to zero and smaller than the number of elements of the Galois Field. FIG. 7 illustrates the 35 first elements of the Galois Field generated by the generator polynomial of degree 32, G(X). The generator polynomial G(X) of degree 32 generates a Galois Field of: EQU 2.sup.32 -1=4,294,967,293 elements
Assuming the CRC-32 code of a data bits stream represented by the polynomial P(X) is Rem.sub.G (P(X)), the corresponding e FCS code based on CRC-32 is: EQU FCS(P(X))=Rem.sub.G (X.sup.32 P(X)+X.sup.k L(X)) EQU k=degree of P(X) EQU L(X)=X.sup.31 +X.sup.30 +. . . +X.sup.2 +X+1
The standard circuitry for computing the FCS of a message is a Linear Feedback Shift Register (LFSR) which carries out a bit by bit multiplication in the Galois Field. Each bit of the message is pushed in the LFSR, Most Significant Bit (MSB) first. The division is performed by the feedbacks. At the end of the process, the FCS (remainder of the division) is within the shift register. This method and type of circuitry is described, for instance in `Error Checking Codes` by Peterson and Weldon, the MIT Press, 2nd edition, 1972. Although simple the method suffers of obvious drawbacks since only one bit is processed at each shift as many shifts as the number of bits is the message is needed in the LFSR. As the 32 bits CRC is used, a 32 bits register is needed. Computing the CRC takes as many clock pulses as there are bits in the message.
A faster CRC calculation is provided in the patent application published under the reference EP 0614 294 entitled `Method for generating a frame check sequence` disclosing a one (or more) byte (s) based FCS calculation, this method being more efficient than a bit based FCS calculation as with the LFSRs. This patent application takes advantage of the properties of the operations in the Galois Fields. As illustrated in FIG. 4, according to the preferred embodiment of the cited patent application, the calculation of FCS of a byte stream can be performed byte by byte, each new byte (42) read being XORed (43) with the result of the multiplication (41) of the previous FCS value by the .alpha..sup.8 element of the Galois Field. The multiplier (41) is the implementation of the .alpha..sup.8 multiplication in the Galois Field, this means modulo the polynomial generator G(X). The mathematical formula illustrating the method is expressed in the Galois Field as follows: EQU FCS(N+1)=FCS(N).times..alpha..sup.8 +B(N+1) (expression 1)
Where FCS(N) is the FCS of the message consisting of the N previous bytes, B(N+1) the polynomial representation of the next byte (new byte) of the message.
.times. is the sign of the polynomial multiplication in the Galois Field. It is a two steps operation comprising a first step to multiply or add the two polynomials and a second step to take the remainder of the result in the division by G. PA1 .alpha. is an irreducible polynomial, root of the Galois Field generated by G. PA1 .alpha..sup.8 is the 9th element of the Galois Field. PA1 receiving one packet of the message, and PA1 calculating the FCS of the payload read in the packet, PA1 in parallel to the previous step
This byte by byte calculation of the FCS can be efficiently used in the access node at the entry of the ATM network for a given AAL5 type connection, to calculate the FCS of one message received. As the messages received in the reassembling access node are segmented, the FCS checking is performed `on the fly` in this node, at each reception of a new cell and not when all the cells have been received. If applied to FCS checking, the method of the cited best prior art will imply the following cell process: at the reception of the first cell of the message, the FCS is calculated byte by byte from the bytes stream of the cell payload according, for example, to the method of FIG. 4; the result is then stored in the control block of the connection as an `intermediate FCS`. At reception of each new cell the `intermediate FCS` is read from the connection control block and a new `intermediate FCS` is calculated from the previous `intermediate FCS` value and from the received cell payload still using one method of the prior art; the updated `intermediate FCS` is stored back in the control block of the connection. When the last cell is read the result of the calculation according to the process just described returns the final expected value of the FCS checking.
The FCS checking which is performed in the adapter cards of the access nodes at the output of the ATM network should be efficient enough to allow the support of high speed links. As an example, with (OC3) 155.52 Mbps links the elapsed time between cells arrival is 2.7 .mu.s; 0.7 .mu.s only are available for cell processing on OC12 links (622.06 Mbps). Even with the improved method of FCS byte(s) by byte(s) calculation of the prior art, it is necessary to be able to perform the intermediate FCS calculation as described during the 2.7 .mu.s left for each cell processing. With the FCS checking process just described, one new `intermediate FCS` calculation cannot start before the previous `intermediate FCS` value has been read in the Control Block of the connection which needs to be fetched. This later operation is illustrated in FIG. 3; it consists first in reading the Virtual Path Identifier (VPI of 8 or 12 bits) and the Virtual Channel Identifier (VCI) identifying the connection in the cell header then a sort is performed in a Search Connection Table to find the Connection Control Block address corresponding to the connection identified; the Connection Control Block is fetched and in this block, the `intermediate FCS` is read; this value is the FCS calculated during the reception of the preceding cell. Fetching the control block and reading the intermediate FCS value takes a significant part of the time available for cell processing. Once the intermediated FCS value is read the new intermediate FCS value is calculated and other cell processing steps need to be performed in the remaining time period. As a matter of fact, the constraints on the number of processing cycles depend on the power of processors (time cycle) used in the apparatus implementing the FCS checking (usually node adapter cards). Other computing resources needs such as storage means also have to be compatible with the type of equipment used for implementation.
Thus, with the method of the prior art and the current technologies, it is very difficult to perform the intermediate FCS calculations for data integrity checking of messages conveyed in AAL5 type cells (and more generally for fixed size packets) in ATM networks (and more generally packet networks) during the cell (packet) processing time available with medium and high speed lines (OC3 and above).
It is a first object of the invention to calculate the FCS of a message segmented over a data packet stream.
It is a second object of the invention to split the FCS calculation of the message into `intermediate FCS` calculation steps performed at each reception of a packet and in an efficient way to support medium and high speed line speed.
It is another object of the invention to perform the FCS calculation using a minimum of other computing resources such as storage.